/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2023-02-11
 * Time: 11:03
 */
/*自定义哈希表
1.K-V 键值对象的存储(保存null k  null value)
2.K 的重复问题
3.哈希表的扩容问题
*/
public class My_HashMap<K, V> {
    static class Node<K, V> {
        public K key;
        public V value;
        public Node<K, V> next;
        
        public Node(K key, V val) {
            this.key = key;
            this.value = val;
        }
    }
    
    //底层基于Node数组
    public Node<K, V>[] array;
    //有效长度
    public int usedSize;
    
    //初始化
    public My_HashMap() {
        this.array = (Node<K, V>[]) new Node[4];
    }
    
    //存元素
    public void put(K key, V val) {
        int hash = key.hashCode();
        int index = hash % array.length;
        //第一次哈希的节点
        Node<K, V> cur = array[index];
        while (cur != null) {
            if (cur.key.equals(key)) {
                cur.value = val;
                return;
            }
            cur = cur.next;
        }
        Node<K, V> newNode = new Node<>(key, val);
        newNode.next = array[index];
        array[index] = newNode;
        this.usedSize++;
        if (loadFactor() > 0.75) {
            reSize();
        }
    }
    
    //扩容
    private void reSize() {
        Node[] newArray = new Node[this.array.length * 2];
        for (int i = 0; i < this.array.length; i++) {
            Node<K, V> cur = array[i];
            while (cur != null) {
                int hash = cur.key.hashCode();
                int index = hash % this.array.length;
                Node<K, V> curNext = cur.next;
                cur.next = newArray[index];
                newArray[index] = cur;
                cur = curNext;
            }
        }
        this.array = newArray;
    }
    
    private double loadFactor() {
        return this.usedSize / this.array.length * 1.0;
    }
    
    //取元素
    public V get(K key) {
        int hash = key.hashCode();
        int index = hash % array.length;
        Node<K, V> cur = array[index];
        while (cur != null) {
            if (cur.key.equals(key)) {
                return cur.value;
            }
            cur = cur.next;
        }
        return null;
    }
    
    public static void main(String[] args) {
        My_HashMap<Integer, String> myHashMap = new My_HashMap<>();
        myHashMap.put(1, "a");
        myHashMap.put(2, "b");
        myHashMap.put(3, "c");
        System.out.println(myHashMap.get(2));
        myHashMap.put(4, "d");
        myHashMap.put(5, "e");
        System.out.println(myHashMap.get(5));
    }
}
